package lcr;

import java.util.ArrayDeque;

public class Test0056 {
}

class Solution0056_1 {
    public boolean findTarget(TreeNode root, int k) {
        ArrayDeque<TreeNode> ld = new ArrayDeque<>();
        ArrayDeque<TreeNode> rd = new ArrayDeque<>();

        TreeNode temp = root;
        while (temp != null){
            ld.offer(temp);
            temp = temp.left;
        }

        temp = root;
        while (temp != null){
            rd.offer(temp);
            temp = temp.right;
        }

        int l = ld.peekLast().val, r = rd.peekLast().val;
        while (l < r){
            int sum = l + r;
            if (sum == k) return true;
            else if (sum < k) l = next(ld,true);
            else r = next(rd,false);
        }
        return false;
    }

    private int next(ArrayDeque<TreeNode> d, boolean b) {
        TreeNode temp = b ? d.pollLast().right : d.pollLast().left;
        while (temp != null){
            d.offer(temp);
            temp = b ? temp.left : temp.right;
        }
        return d.peekLast().val;
    }
}
